package com.ronz.linkedlist;

import com.ronz.linkedlist.util.HeroNode;
import com.ronz.linkedlist.util.NodeUtil;

/**
 * @Description 实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的编号。
 *              例如：
 *                  输入： 1->2->3->4->5 和 k = 2
 *                  输出： 4
 * @Author Ronz
 * @Date 2020/12/22 15:05
 * @Version 1.0
 */
public class No2_PenTest_SingleLinkedList {

    public static void main(String[] args) {
        // 构造头结点
        HeroNode head = NodeUtil.getTestList();
        int item = getItem(head, 2);
        System.out.println(item);
    }

    /**
     * @Description 根据链表的头结点和 k 到链表中查找倒数第 k 个节点
     */
    public static int getItem(HeroNode head, int k){
        // 1. 首先获取链表总长度
        int size = getSize(head);
        // 2. 链表总长度减去 k 个节点，得到要遍历的节点个数
        int length = size - k;
        // 3. 获取头结点
        HeroNode temp = head;
        // 4. 遍历到倒数第 k 个节点
        for (int i=0; i<length+1; i++){
            temp = temp.next;
        }
        return temp.getNo();
    }

    /**
     * @Description 获取链表中的结点的总个数
     */
    public static int getSize(HeroNode head){
        // 1. 获取头结点
        HeroNode temp = head;
        int length = 0;
        // 2. 遍历链表，获取节点个数
        while (true){
            if (temp.next == null){     // 如果到了末尾
                break;
            }
            length++;
            temp = temp.next;
        }
        return length;
    }

}
